#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@UserFor     :   ***    ***
@File        :   easy-70-爬楼梯.py    
@Email       :   18574945291@163.com
@Modify Time :   2021-02-15 15:00
@Author      :   code_wizard (wll) 
"""

# 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
# 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution:

    # 使用递归解法
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1)+self.climbStairs(n-2)

    # 使用动态规划
    def climbStairsWithDP(self, n: int) -> int:
        res = 0
        last_1 = 1
        last_2 = 0
        for i in range(1,n+1):
            res = last_1 + last_2
            last_2,last_1 = last_1,res
        return res
if __name__ == '__main__':
    n = 5
    obj = Solution()
    # print(obj.climbStairs(n))
    print(obj.climbStairsWithDP(n))